// PHYLIP_NEAREST_NEIGHBOR_H
//

#if !defined( PHYLIP_NEAREST_NEIGHBOR_H)
#define  PHYLIP_NEAREST_NEIGHBOR_H

#include <vector>
#include <string>

#include "matrix.h"
#include "components/progress_indicator.h"


namespace phylip_tree
{
	struct t_node
	{
		t_node(): next(0), back(0), is_leaf(false),number(9999), length(-10){}
		t_node *	next;
		t_node *	back;
		bool 		is_leaf;
		long 		number;
		std::string name;
		double		length;
	};
	typedef t_node* pnode;
	
	struct t_phylip_tree
	{
		t_phylip_tree(unsigned cnt_leaves_)
			:vec_node(cnt_leaves_ * 4 - 4),
			cnt_leaves(cnt_leaves_), UPGMA(false), start(0)
			{}
		std::vector<t_node> vec_node;
		std::vector<pnode> nodep;
		unsigned	cnt_leaves;
		bool		UPGMA;
		t_node *	start;
	};
	
	std::string phylip_tree_to_str(t_phylip_tree& cur_tree)	;
	
	
	void phylip_make_tree(	t_phylip_tree& cur_tree,
							const std::vector<std::string>& names,
							t_matrix& matrix);
	void phylip_make_tree(	t_phylip_tree& cur_tree,
							const std::vector<std::string>& names,
							t_matrix& matrix,
							t_progress_indicator& dots);
	
	template<typename TREEMAKER> void phylip_treeout(	TREEMAKER& maker,
														const t_phylip_tree& cur_tree,
														t_node *p)
	{
		assert(p);
		if (p->is_leaf)
		{
			maker.add_leaf(p->name);
			cerr << "add_leaf " << p->back<< "\n";
		}
		else
		{
			cerr << "add_internal_node\n";
			maker.add_internal_node();
			phylip_treeout(maker, cur_tree, p->next->back);
			cerr << "add_sibling\n";
			maker.add_sibling();
			phylip_treeout(maker, cur_tree, p->next->next->back);
			if (p == cur_tree.start && !cur_tree.UPGMA)
			{
				cerr << "add_sibling\n";
				maker.add_sibling();
				phylip_treeout(maker, cur_tree, p->back);
			}
			cerr << "to_grandparent\n";
			maker.reparent_to_grandparent();
		}
		if (p == cur_tree.start)
		{
			cerr << "finish\n";
			maker.finish();
		}
		else
		{
			cerr << "to_grandparent\n";
			maker.set_branch_len(p->length);
		}
	
	}
	
	
};


#endif
